From babd7089ab3a1ac18ad2e1e6801461638cd556dc Mon Sep 17 00:00:00 2001 From: robertl Date: Sat, 7 Oct 2006 23:39:44 +0000 Subject: [PATCH] Paul Fox adapts mergesort for use on our internal linked lists. --- gpsbabel/queue.c | 159 +++++++++++++++++++++++++++++++++++++++++++++++ gpsbabel/queue.h | 2 + gpsbabel/sort.c | 32 ++-------- 3 files changed, 165 insertions(+), 28 deletions(-) diff --git a/gpsbabel/queue.c b/gpsbabel/queue.c index db3c56e6e..1c0b54d65 100644 --- a/gpsbabel/queue.c +++ b/gpsbabel/queue.c @@ -20,6 +20,7 @@ */ #include "queue.h" +#include "stddef.h" void enqueue(queue *new_el, queue *old) @@ -40,3 +41,161 @@ dequeue(queue *element) prev->next = next; return element; } + +/* + * The following sorting code was derived from linked-list mergesort + * sample code by Simon Tatham, code obtained from: + * http://www.chiark.greenend.org.uk/~sgtatham/algorithms/listsort.html + * Modified for use with gpsbabel's queues by Paul Fox, October 2006. + * + * Original description and copyright messages follow... + */ + +/* + * Demonstration code for sorting a linked list. + * + * The algorithm used is Mergesort, because that works really well + * on linked lists, without requiring the O(N) extra space it needs + * when you do it on arrays. + * + * ... + */ + +/* + * This file is copyright 2001 Simon Tatham. + * + * Permission is hereby granted, free of charge, to any person + * obtaining a copy of this software and associated documentation + * files (the "Software"), to deal in the Software without + * restriction, including without limitation the rights to use, + * copy, modify, merge, publish, distribute, sublicense, and/or + * sell copies of the Software, and to permit persons to whom the + * Software is furnished to do so, subject to the following + * conditions: + * + * The above copyright notice and this permission notice shall be + * included in all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, + * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES + * OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND + * NONINFRINGEMENT. IN NO EVENT SHALL SIMON TATHAM BE LIABLE FOR + * ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF + * CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN + * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE + * SOFTWARE. + */ + + +void +sortqueue (queue *qh, int (*cmp)(const queue *, const queue *)) +{ + + queue *p, *q, *e, *tail, *oldhead, *list; + int insize, nmerges, psize, qsize, i; + + /* + * Special case: if `list' is empty, we're done. + */ + if (QUEUE_EMPTY(qh)) + return; + + /* + * The algorithm doesn't really want the extra list head + * element. So remove the list head for now. Put it back later. + */ + + list = QUEUE_FIRST(qh); + dequeue(qh); + + insize = 1; + + while (1) { + p = list; + oldhead = list; /* only used for circular linkage */ + list = NULL; + tail = NULL; + + nmerges = 0; /* count number of merges we do in this pass */ + + while (p) { + nmerges++; /* there exists a merge to be done */ + /* step `insize' places along from p */ + q = p; + psize = 0; + for (i = 0; i < insize; i++) { + psize++; + q = (q->next == oldhead ? NULL : q->next); + if (!q) break; + } + + /* if q hasn't fallen off end, we have + * two lists to merge */ + qsize = insize; + + /* now we have two lists; merge them */ + while (psize > 0 || (qsize > 0 && q)) { + + /* decide whether next element of + * merge comes from p or q + */ + if (psize == 0) { + /* p is empty; e must come from q. */ + e = q; q = q->next; qsize--; + if (q == oldhead) q = NULL; + } else if (qsize == 0 || !q) { + /* q is empty; e must come from p. */ + e = p; p = p->next; psize--; + if (p == oldhead) p = NULL; + } else if (cmp(p,q) <= 0) { + /* First element of p is + * lower (or same); e must + * come from p. + */ + e = p; p = p->next; psize--; + if (p == oldhead) p = NULL; + } else { + /* First element of q is + * lower; e must come from + * q. + */ + e = q; q = q->next; qsize--; + if (q == oldhead) q = NULL; + } + + /* add the next element to the merged list */ + if (tail) { + tail->next = e; + } else { + list = e; + } + + /* Maintain reverse pointers in a + * doubly linked list. */ + e->prev = tail; + + tail = e; + } + + /* now p has stepped `insize' places + * along, and q has too */ + p = q; + } + tail->next = list; + list->prev = tail; + + /* If we have done only one merge, we're finished. + * Allow for nmerges==0, the empty list case. + */ + if (nmerges <= 1) { + + /* Put the list head back at the start of the list */ + ENQUEUE_TAIL(list, qh); + return; + + } + + /* Otherwise repeat, merging lists twice the size */ + insize *= 2; + } +} diff --git a/gpsbabel/queue.h b/gpsbabel/queue.h index cf73f95b6..51250d1d8 100644 --- a/gpsbabel/queue.h +++ b/gpsbabel/queue.h @@ -27,6 +27,8 @@ typedef struct queue { void enqueue(queue *new_el, queue *old); queue * dequeue(queue *element); +void sortqueue (queue *qh, int (*cmp)(const queue *, const queue *)); + #define QUEUE_INIT(head) (head)->next = ((head)->prev = head) #define QUEUE_FIRST(head) ((head)->next) #define QUEUE_NEXT(element) ((element)->next) diff --git a/gpsbabel/sort.c b/gpsbabel/sort.c index b7e579431..52c9bd810 100644 --- a/gpsbabel/sort.c +++ b/gpsbabel/sort.c @@ -49,10 +49,10 @@ arglist_t sort_args[] = { }; static int -sort_comp(const void * a, const void * b) +sort_comp(const queue * a, const queue * b) { - const waypoint *x1 = *(waypoint **)a; - const waypoint *x2 = *(waypoint **)b; + const waypoint *x1 = (waypoint *)a; + const waypoint *x2 = (waypoint *)b; switch (sort_mode) { case sm_gcid: return x1->gc_data.id - x2->gc_data.id; @@ -66,31 +66,7 @@ sort_comp(const void * a, const void * b) void sort_process(void) { - queue * elem, * tmp; - waypoint ** comp; - int i = 0, wc; - - wc = waypt_count(); - - comp = (waypoint **) xcalloc(wc, sizeof(*comp)); - - QUEUE_FOR_EACH(&waypt_head, elem, tmp) { - comp[i] = (waypoint *)elem; - waypt_del(comp[i]); /* Pop this waypoint off the master Q */ - i++; - } - - qsort(comp, wc, sizeof(waypoint *), sort_comp); - - /* - * Now re-add the list back. - */ - for (i = 0; i < wc ; i++) { - waypt_add(comp[i]); - } - - if (comp) - xfree(comp); + sortqueue(&waypt_head, sort_comp); } void -- 2.30.2